package 链表题目;

import 链表题目.model.ListNode;

import java.util.PriorityQueue;


// 合并K个升序链表
//https://leetcode.cn/problems/merge-k-sorted-lists/description/
class 合并K个升序链表 {
    // 两两合并
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        ListNode ans = new ListNode(0, lists[0]);
        for (int i = 1; i < lists.length; i++) {
            ListNode temp = ans;
            ListNode list1 = lists[0];
            ListNode list2 = lists[i];
            while (list1 != null || list2 != null) {
                if (list1 == null) {
                    temp.next = list2;
                    break;
                }
                if (list2 == null) {
                    temp.next = list1;
                    break;
                }
                if (list1.val < list2.val) {
                    temp.next = list1;
                    list1 = list1.next;
                } else {
                    temp.next = list2;
                    list2 = list2.next;
                }
                temp = temp.next;
            }
            lists[0] = ans.next;
        }
        return ans.next;
    }

    // 优先队列最小堆方法
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b) -> (a.val - b.val)
        );
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

    //  分治合并
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
//        0 8
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
//        4
//        2   6
//        1   3  5  7
//        0
        int mid = (l + r) >> 1;
//        0 4   5 8
//        0 2 3 4  5 6 7 8
//        0 1  2 2  3 3 4 4  5 5 6 6  7 7 8 8
//        0 0 1 1
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, list1 = a, list2 = b;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null ? list1 : list2);
        return head.next;
    }

}
